package demo1_binaryserach;

import java.util.Arrays;

public class MyArray {
    private int[] elements;
    public  MyArray(){
        elements = new int[0];
    }
    public int size (){
        return elements.length;
    }
    //在尾部添加一个元素
    public void add (int element){
        //        创建一个新的数组
        int[] newArr = new int[elements.length+1];
        //         把原数组中的元素复制到新数组中
        for (int i = 0; i< elements.length;i++)
            newArr[i] = elements[i];
        //    把添加的元素放入新数组内
        newArr[elements.length] = element;
        //        使用新数组替换旧数组
        elements = newArr;
    }

    public void delete (int index){
        if (index < 0 ||  index > elements.length)
            throw new RuntimeException("下标越界异常");
        int[] newArray = new int[elements.length-1];
        for (int i = 0 ; i < newArray.length ; i++)
        {
            if (i < index)
            newArray[i]=elements[i];
            else newArray[i]=elements[i+1];
        }
        elements = newArray;
    }

    public void set (int index,int element){
        if (index < 0 ||  index > elements.length)
            throw new RuntimeException("下标越界异常");
        elements[index] = element;
    }

    /**
     * 查找元素  返回下标
     * @param target
     * @return
     */
    public int search (int target) {
        if (target < 0 || target > elements.length)
            throw new RuntimeException("下标越界异常");

        for (int i = 0; i < elements.length; i++)
            if (elements[i] == target)
                return i;
        return -1;
    }

    /**
     * 查找元素的下标
     * @param target
     * @return
     */
    public int binarySearch (int target){
        int begin = 0;
        int end =elements.length-1;
        int mid = (begin+ end)/2;
        while (true){
            if (begin > end)
                return  -1;
            //判断是不是要查找的元素
            if (elements[mid]==target) {
                return mid;
            }
            //中间这个元素不是要查找的元素
            else {
                //判断中间这个元素是不是大于目标元素
                if (elements[mid]>target)
                    end = mid-1;
                //不是的话？
                else if(elements[mid]<target)
                    begin =mid+1 ;
            }
            //取出新的中间位置
            mid = (begin+ end)/2;
        }
    }

    public void show (){
        System.out.println(Arrays.toString(elements));
    }
}
